﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Diagnostics;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Xml;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace MoveBox
{
    public partial class MainForm : Form
    {
        //Dictionary<char, SolidBrush> brushMap = new Dictionary<char, SolidBrush>();
        Dictionary<char, Color> colorMap = new Dictionary<char, Color>();
        List<Color> colorList = new List<Color>() { Color.Yellow, Color.Brown, Color.DarkGreen, Color.DarkOrange, Color.DarkTurquoise, Color.DimGray, Color.Firebrick, Color.Azure, };
        const int BlockSize = 80;
        private Board board;

        public MainForm()
        {
            InitializeComponent();
            LoadFiles();
        }
        void LoadFiles()
        {
            foreach (var item in Directory.EnumerateFiles("Level"))
            {
                var fileName = Path.GetFileName(item);
                var ext = Path.GetExtension(fileName);

                if (".xml".Equals(ext))
                {
                    cbFile.Items.Add(Path.GetFileNameWithoutExtension(fileName));
                }
            }
        }
        void Draw()
        {
            this.canvas.Width = board.M * BlockSize;
            this.canvas.Height = board.N * BlockSize;
            this.Width = Math.Max(this.canvas.Width + 40, this.Width);
            this.Height = Math.Max(this.canvas.Height + 120, this.Height);

            using (Graphics g = this.canvas.CreateGraphics())
            {
                g.Clear(SystemColors.ButtonHighlight);
                //brushMap.Clear();
                for (var i = board.N - 1; i >= 0; i--)
                {
                    for (var j = board.M - 1; j >= 0; j--)
                    {
                        if (board.Data[i, j] != Board.EMPTY)
                        {
                            var c = board.Data[i, j];
                            if (!colorMap.ContainsKey(c))
                            {
                                colorMap[c] = colorList.ElementAt(colorMap.Count);
                            }
                            using (var brush = new SolidBrush(colorMap[c]))
                            {
                                g.FillRectangle(brush, j * BlockSize, i * BlockSize, BlockSize, BlockSize);
                            }

                            //g.DrawRectangle(new Pen(colorMap[c]), j * BlockSize, i * BlockSize, BlockSize, BlockSize);
                            g.DrawString(string.Format("({0},{1})", i.ToString(), j.ToString()),
                                this.Font, Brushes.Black, j * BlockSize + BlockSize / 2 - 16, i * BlockSize + BlockSize / 2 - 4);
                        }
                    }
                }
            }
            board.Print();
        }

        private void btnSolve_Click(object sender, EventArgs e)
        {
            Task.Run(() =>
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                if (board.Solve())
                {
                    Console.WriteLine("find");
                }
                else
                {
                    Console.WriteLine("can't find");
                    //MessageBox.Show("can't find");
                }
                sw.Stop();
                TimeSpan ts = sw.Elapsed;
                string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
                Console.WriteLine("RunTime " + elapsedTime);
            });

        }

        private void cbFile_SelectedIndexChanged(object sender, EventArgs e)
        {
            var fileName = cbFile.Text;
            var filePath = Path.Combine("Level", fileName + ".xml");
            if (File.Exists(filePath))
            {
                XmlDocument xml = new XmlDocument();
                xml.Load(filePath);

                foreach (XmlNode item in xml.GetElementsByTagName("level"))
                {
                    cbLevel.Items.Add(item.Attributes["id"].InnerText);
                }
            }
        }

        private void cbLevel_SelectedIndexChanged(object sender, EventArgs e)
        {
            var fileName = cbFile.Text;
            var filePath = Path.Combine("Level", fileName + ".xml");
            if (File.Exists(filePath))
            {
                XmlDocument xml = new XmlDocument();
                xml.Load(filePath);

                foreach (XmlNode node in xml.GetElementsByTagName("level"))
                {
                    if (node.Attributes["id"].InnerText == cbLevel.Text)
                    {
                        int step = Convert.ToInt32(node.Attributes["goal"].InnerText);
                        lblStep.Text = node.Attributes["goal"].InnerText;
                        List<Box> boxes = new List<Box>();


                        Box minBox = new Box() { X = 8, Y = 8 };
                        Box maxBox = new Box() { X = 0, Y = 0 };
                        foreach (XmlNode child in node.ChildNodes)
                        {
                            if ("box".Equals(child.Name))
                            {
                                var box = new Box()
                                {
                                    X = Convert.ToInt32(child.Attributes["x"].InnerText),
                                    Y = Convert.ToInt32(child.Attributes["y"].InnerText),
                                    Type = Convert.ToInt32(child.Attributes["type"].InnerText)
                                };
                                boxes.Add(box);
                                minBox.X = Math.Min(minBox.X, box.X);
                                minBox.Y = Math.Min(minBox.Y, box.Y);

                                maxBox.X = Math.Max(maxBox.X, box.X);
                                maxBox.Y = Math.Max(maxBox.Y, box.Y);
                            }
                        }
                        int N = maxBox.Y - minBox.Y + 1;
                        int M = maxBox.X - minBox.X + 3;
                        char[,] data = new char[N, M];

                        foreach (var box in boxes)
                        {
                            data[box.Y - minBox.Y, box.X - minBox.X + 1] = (char)(box.Type + 65);
                        }
                        for (var i = 0; i < N; i++)
                        {
                            for (var j = 0; j < M; j++)
                            {
                                if (data[i, j] == '\0')
                                {
                                    data[i, j] = '.';
                                }
                            }
                        }
                        board = new Board(step, data);
                        Draw();
                        break;
                    }
                }
            }
            else
            {
                MessageBox.Show("找不到文件");
            }
        }
    }
    public struct Box
    {
        public int X { get; set; }
        public int Y { get; set; }
        public int Type { get; set; }
    }
    public class Board
    {
        static readonly int[,] d = { { 1, 0 }, { 0, 1 }, { 0, -1 } };
        public const char EMPTY = '.';
        public char[,] Data { get; set; }
        public int N { get; set; }
        public int M { get; set; }

        public Board Prev { get; set; }
        public string SwapString { get; set; }
        public int Turn { get; set; }

        public Board(int step, char[,] data)
        {
            Turn = step;
            Data = data;
            N = data.GetLength(0);
            M = data.GetLength(1);
        }
        public Board(IEnumerable<string> lines)
        {
            Turn = Int32.Parse(lines.ElementAt(0));
            N = lines.Count() - 1;
            M = lines.ElementAt(1).Length;
            Data = new char[N, M];
            for (var i = 0; i < N; i++)
            {
                for (var j = 0; j < M; j++)
                {
                    Data[i, j] = lines.ElementAt(i + 1)[j];
                }
            }
        }
        private bool InArea(int x, int y)
        {
            return x >= 0 && y >= 0 && x < N && y < M;
        }
        public Board(Board current, Board prev, string swapString)
        {
            this.N = current.N;
            this.M = current.M;
            this.Data = new char[N, M];
            for (var i = 0; i < N; i++)
            {
                for (var j = 0; j < M; j++)
                {
                    Data[i, j] = current.Data[i, j];
                }
            }
            Prev = prev;
            SwapString = swapString;
        }

        public void Print(string msg = null)
        {
            if (!string.IsNullOrWhiteSpace(msg))
            {
                Console.WriteLine(msg + "-----");
            }
            for (var i = 0; i < N; i++)
            {
                for (var j = 0; j < M; j++)
                {
                    Console.Write(Data[i, j]);
                }
                Console.Write(Environment.NewLine);
            }
        }
        public void Swap(int x, int y, int x1, int y1)
        {
            char c = Data[x, y];
            Data[x, y] = Data[x1, y1];
            Data[x1, y1] = c;
        }
        public bool IsWin()
        {
            for (var i = 0; i < N; i++)
            {
                for (var j = 0; j < M; j++)
                {
                    if (Data[i, j] != EMPTY)
                    {
                        return false;
                    }
                }
            }

            ShowSwapString();
            return true;
        }
        void ShowSwapString()
        {
            if (Prev != null)
            {
                Prev.ShowSwapString();
            }
            Console.WriteLine(SwapString);
        }
        public bool Solve()
        {
            return Solve(this, Turn);
        }
        private bool Solve(Board current, int turn)
        {
            if (turn == 0)
            {
                return current.IsWin();
            }
            if (current.IsWin())
            {
                return true;
            }
            for (var i = 0; i < N; i++)
            {
                for (var j = 0; j < M; j++)
                {
                    if (Data[i, j] != EMPTY)
                    {
                        for (var k = 0; k < 3; k++)
                        {
                            var newX = i + d[k, 0];
                            var newY = j + d[k, 1];
                            if (InArea(newX, newY) && Data[i, j] != Data[newX, newY])
                            {
                                string swapString = string.Format("swap ({0},{1}) and ({2},{3})", i, j, newX, newY);
                                var m = new Board(current, current, swapString);
                                m.Swap(i, j, newX, newY);
                                //m.Print("swap");
                                m.Run();
                                if (Solve(m, turn - 1))
                                {
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
            return false;

        }
        void Run()
        {
            do
            {
                Drop();
            } while (Match() && !IsWin());
        }
        void Drop()
        {
            for (var j = 0; j < M; j++)
            {
                var cur = N - 1;
                for (var i = N - 1; i >= 0; i--)
                {
                    if (Data[i, j] != EMPTY)
                    {
                        Data[cur, j] = Data[i, j];
                        cur--;
                    }
                }
                for (; cur >= 0; cur--)
                {
                    Data[cur, j] = EMPTY;
                }
            }
            //Print("drop");
        }
        bool Match()
        {
            bool hasMatch = false;
            bool[,] tag = new bool[N, M];
            for (var i = 0; i < N; i++)
            {
                for (var j = 0; j < M; j++)
                {
                    if (Data[i, j] != EMPTY)
                    {
                        if (InArea(i + 1, j) && InArea(i + 2, j) && Data[i + 1, j] == Data[i, j] && Data[i + 2, j] == Data[i, j])
                        {
                            tag[i, j] = true;
                            tag[i + 1, j] = true;
                            tag[i + 2, j] = true;
                            hasMatch = true;
                        }
                        if (InArea(i, j + 1) && InArea(i, j + 2) && Data[i, j + 1] == Data[i, j] && Data[i, j + 2] == Data[i, j])
                        {
                            tag[i, j] = true;
                            tag[i, j + 1] = true;
                            tag[i, j + 2] = true;
                            hasMatch = true;
                        }
                    }
                }
            }
            for (var i = 0; i < N; i++)
            {
                for (var j = 0; j < M; j++)
                {
                    if (tag[i, j])
                    {
                        Data[i, j] = EMPTY;
                    }
                }
            }
            //Print("match");
            return hasMatch;
        }
    }
}
